/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// 二叉树是否为对称二叉树?
// 其实这一道题目,需要用到6里面的相同的树的算法: 因为找对称二叉树就相当于比对树的两边是否是相同的
// 我们需要了解对称二叉树的结构是怎么样的: 一棵树,其节点的左子节点和右子节点之后的延伸都是相同的节点
// 例如:     1
//          2 2
//        3 4 3 4
//      56 56 56 56
// 如何之后的节点有任何一个不对称都不算对称二叉树

// 我们了解了,思路该如何解决呢?
// 其实非常简单,我们从根节点开始的左右子节点开始使用递归
// 通过比对左节点的左子节点、右节点的右子节点 和 左节点的右子节点、右节点的左子节点,一直比对下去
// 这样子就可以验证是否是左右对称了

bool isSameTree (struct TreeNode* p , struct TreeNode* q)
{

    if (p == NULL && q == NULL) // 如果左右节点同时为空,返回真
    {

        return true ;

    }

    if (p == NULL || q == NULL) // 只有一个节点不为空就返回假
    {

        return false ;

    }

    if (p -> val != q -> val) // 结构对不上就返回假
    {

        return false ;

    }

    return isSameTree (p -> left , q -> right ) && isSameTree (p -> right , q -> left) ; // 依次递归

}
bool isSymmetric(struct TreeNode* root) 
{

    return isSameTree (root -> left , root -> right) ;
    
}